Pattern matching is the application of analytical rules to a block of data to identify a feature of that block of data. Data compression in networks, which transmit data between computer systems, often involves transmitting data using an encoding scheme or compression algorithm that utilizes pattern matching to compress the data and reduce the amount of bandwidth and receiver buffer space necessary for transmission of the data. For example, a Lempel-Ziv Stac algorithm is an example a data compression encoding scheme that utilizes pattern matching.
The Lempel-Ziv Stac algorithm searches an incoming data stream for repeating data patterns by comparing the incoming data intended for transmission to a history buffer, or dictionary, maintained at a transmitter side of the link. Repetitive data patterns are replaced by a token of shorter length; this token usually consists of a pointer to the repetitive data's matching location in the history buffer and a length of the matching data sequence.
For example, the transmitter might maintain a history of the past 1 Kbyte of data frames, and whenever a new data sequence is input to the compressor, this history may be searched for matching data sequences. Instead of transmitting the actual data, a token might be generated which effectively states, “go back 150 bytes in the history and transmit the next 10 bytes.” At the receiver side of the link, a decompressor recreates an exact replica of the compressor's dictionary and uses the tokens provided by the data stream to invert the compression operation.
Therefore, the tokens can be viewed as pointers into the 1 Kbyte data history. The history files at both ends of the link should match; otherwise, the decompressor pointer token will output meaningless data. Thus, future data is compressed based on the previous data history. Typical compression ratios vary with the type of data and amount of redundancy present. Completely random data will not be compressed very much at all, while highly redundant traffic with a lot of idle characters may experience a very large improvement. Data compression efficiency thus depends on the pattern matching.
Accordingly, there exists a need in the art to overcome the deficiencies and limitations described hereinabove.